#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int st[1000005][20];
int LOG[1000005];

void init(int arr[], int n)
{
    for (int i = 2; i <= n; i++)
    {
        LOG[i] = LOG[i / 2] + 1;
    }
    for (int i = 1; i <= n; i++)
    {
        st[i][0] = arr[i];
    }
    for (int e = 1; e < 20; e++)
    {
        for (int i = 1; i + (1 << e) - 1 <= n; i++)
        {
            st[i][e] = max(st[i][e - 1], st[i + (1 << (e - 1))][e - 1]);
        }
    }
}

int query(int l, int r)
{
    if (l > r)
        return INT_MIN;
    int e = LOG[r - l + 1];
    return max(st[l][e], st[r - (1 << e) + 1][e]);
}